|
In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to the edges or vertices, or both, of a graph. Formally, given a graph ''G = (V, E)'', a vertex labeling is a function of ''V'' to a set of ''labels''. A graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labeling is a function mapping ''E'' to a set of labels. In this case, ''G'' is called an edge-labeled graph. When the edge labels are members of an ordered set (e.g., the real numbers), it may be called a weighted graph. When used without qualification, the term labeled graph generally refers to a vertex-labeled graph with all labels distinct. Such a graph may equivalently be labeled by the consecutive integers , where ''n'' is the number of vertices in the graph.〔 For many applications, the edges or vertices are given labels that are meaningful in the associated domain. For example, the edges may be assigned weights representing the "cost" of traversing between the incident vertices.〔"Different Aspects of Coding Theory", by Robert Calderbank (1995) ISBN 0-8218-0379-4, (p. 53 )"〕 In the above definition a graph is understood to be a finite undirected simple graph. However, the notion of labeling may be applied to all extensions and generalizations of graphs. For example, in automata theory and formal language theory it is convenient to consider labeled multigraphs, i.e., a pair of vertices may be connected by several labeled edges.〔"Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, (p. 313 ) 〕 ==History== Most graph labelings trace their origins to labelings presented by Alex Rosa in his 1967 paper. Rosa identified three types of labelings, which he called α-, β-, and ρ-labelings. β-Labelings were later renamed graceful by S.W. Golomb and the name has been popular since. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「graph labeling」の詳細全文を読む スポンサード リンク
|